package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/11/25.<br><br>
 *
 * 中等：单词搜索
 */
public class Topic79 {

    public static void main(String[] args) {
        Topic79 instance = new Topic79();
        char[][] array;

        array = new char[][] {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        System.out.println(instance.exist(array, "ABCCED"));
        System.out.println(instance.exist(array, "SEE"));
        System.out.println(instance.exist(array, "ABCB"));
    }

    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];

        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(helper(board, visited, i, j, word, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean helper(char[][] board, boolean[][] visited, int i, int j, String word, int k) {
        if(board[i][j] != word.charAt(k)) {
            return false;
        }
        else if(k == word.length() - 1) {
            return true;
        }

        boolean result = false;
        visited[i][j] = true;

        int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for(int[] array : direction) {
            int newI = i + array[0];
            int newJ = j + array[1];

            if(newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length) {
                if(!visited[newI][newJ]) {
                    boolean flag = helper(board, visited, newI, newJ, word, k + 1);
                    if(flag) {
                        result = true;
                        break;
                    }
                }
            }
        }

        visited[i][j] = false;
        return result;
    }
}
